package leetcode每日一题;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * 1. 问题描述
 *      给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，
 *      其中每个子序列都由连续整数组成且长度至少为 3 。
 *
 * 2，算法分析
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 分割数组为连续子序列 {
    public static void main(String[] args) {
        System.out.println(0 ^ 3);
    }

    public static boolean test(int[] nums) {
        if (nums.length <= 2) {return false;}
        HashMap<Integer,Integer> countMap = new HashMap<>();
        for (int num : nums) { countMap.put(num,countMap.getOrDefault(num,0)+1);}
        if (countMap.size() == nums.length) {return true;} // 都是单个元素
        for (int i = 0; i < nums.length; i++) {
            // 以当前元素为起点的子序列
            if (countMap.get(nums[i]) > 0) {
                countMap.put(nums[i],countMap.getOrDefault(nums[i],0)-1);
            }
        }
        return true;
    }

    /**
     *
     * 思路分析：
     *      首先题目的含义是：
     *          判断一个数组能否分成严格单调的子序列的，子序列的长度至少为3
     *          其中数组中的每个元素只能使用一次
     *      具体的例子：
     *          例1[1,2,3,3,4,5], 我们可以将该序列分成 [1,2,3] [3,4,5]
     *          例2[1,2,3,3,4,4,5,5], 我们可以将序列分成 [1,2,3,4,5] [3,4,5]
     *      分析算法思路：
     *          我们最希望看到的情况就是[1,2,3,4,5]这样的，直接可以返回最大的子序列
     *          但是，对于一般的情况nums中会有重复的元素，我们还是按照上面的情况，每次
     *          找到最大的满足条件的子序列
     *          具体而言：
     *              如果我们能判断当前的元素可以构成一个至少长度为3的子序列的起点
     *              例如以n开头，n+1，n+2在数组中还有元素没有使用完，此时我们就已经
     *              找到了一个满足条件的子序列，为了让这个子序列尽可能的长，我们可以
     *              判断下一个元素是否可以添加到当前已经构建好的子序列中，如果能，修改
     *              当前序列的尾部元素
     *           此时我们的策略就是：
     *              如果当前元素可以添加到已经构建好的子序列中，就添加进去
     *              如果当前元素无法添加到已经构建好的子序列中，判断该元素能否作为新的序列的起点
     *      算法实现
     *          1. 初始化两个Map，分别为countMap和tailMap
     *              countMap：记录nums中元素的出现次数
     *              tailMap：记录以当前元素结尾的子序列的次数
     *          2. 策略
     *              1. 判断当前元素的个数是否大于0，如果等于0，直接跳过当前元素
     *              2. 判断当前元素-1为结尾的序列个数是否为0，如果不为0，说明当前元素可以
     *                 构成新的序列的结尾
     *                 此时我们有四个更新：
     *                  1. countMap中对应当前元素的次数-1
     *                  2. 当前元素的个数-1
     *                  3. 以当前元素-1为结尾的子序列的个数-1
     *                  4. 以当前元素为结尾的子序列的个数+1
     *              3. 如果不能添加，判断当前元素能否作为新的子序列的起点
     *                  可以构成的条件：当前元素+1和当前元素+2的个数都大于0
     *                  更新countMap，tailMap
     *              4. 如果既不能添加到已经构建好的，又不能作为新的子序列的起点，说明当前数组无法划分
     *                 直接返回false即可
     * @param nums
     * @return
     */
    public static boolean isPossible1(int[] nums) {
        // countMap的作用是记录nums中元素的个数
        HashMap<Integer,Integer> countMap = new HashMap<>();
        // tailMap的作用是记录以当前元素结尾的子序列的个数
        HashMap<Integer,Integer> tailMap = new HashMap<>();
        // 扫描计数
        for(int num : nums) {
            countMap.put(num,countMap.getOrDefault(num,0)+1);
        }
        // 扫描数组
        for(int num : nums) {
            // 判断当前元素个数
            if(countMap.getOrDefault(num,0) == 0) {
                continue;
            }
            // 判断当前元素能后加到已经构建好的子序列中
            if(tailMap.getOrDefault(num,0) > 0) {
                // 此时说明可以
                tailMap.put(num,tailMap.getOrDefault(num,0)-1);
                tailMap.put(num+1,tailMap.getOrDefault(num+1,0)+1);
            }
            // 判断当前元素能否作为新的子序列的起点
            else if(countMap.getOrDefault(num+1,0) > 0 && countMap.getOrDefault(num+2,0) > 0) {
                // 此时说明可以
                // 将countMap对应的元素的出现次数-1
                countMap.put(num+1,countMap.getOrDefault(num+1,0)-1);
                countMap.put(num+2,countMap.getOrDefault(num+2,0)-1);
                // 由于当前num可以构成一个子序列，并且该序列以num+2结尾
                //
                tailMap.put(num+3,tailMap.getOrDefault(num+3,0)+1);
            } else {
                return false;
            }
            countMap.put(num,countMap.getOrDefault(num,0)-1);
        }
        return true;
    }

    public static boolean isPossible2(int[] nums) {
        HashMap<Integer,Integer> countMap = new HashMap<>();
        HashMap<Integer,Integer> tailMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num,countMap.getOrDefault(num,0)+1);
        }
        for (int num : nums) {
            if (countMap.getOrDefault(num,0) == 0) {
                continue;
            }
            else if (tailMap.getOrDefault(num-1,0) > 0) {
                countMap.put(num,countMap.getOrDefault(num,0)-1);
                tailMap.put(num-1,tailMap.getOrDefault(num-1,0)-1);
                tailMap.put(num,tailMap.getOrDefault(num,0)+1);
            }
            else if (countMap.getOrDefault(num+1,0) > 0
                  && countMap.getOrDefault(num+2,0) > 0 ) {
                countMap.put(num,countMap.getOrDefault(num,0)-1);
                countMap.put(num+1,countMap.getOrDefault(num+1,0)-1);
                countMap.put(num+2,countMap.getOrDefault(num+2,0)-1);
                tailMap.put(num+2,tailMap.getOrDefault(num+2,0)+1);
            }
            else {
                return false;
            }
            // countMap.put(num,countMap.getOrDefault(num,0)-1);
        }
        return true;
    }
}
